import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Test {

    /*
     * 三数之和
     * */

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum(nums));
    }

    //排序 + 暴力搜索 + 利用 set 去重
//    public static int[] threeSum(int[] nums) {
//        Arrays.sort(nums);
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i + 1; j < nums.length; j++) {
//                for (int k = j + 1; k < nums.length - 1; k++) {
//                    int sum = nums[i] + nums[j] + nums[k];
//                    if(sum == 0){
//                        return new int[]{nums[i],nums[j],nums[k]};
//                    }
//                }
//            }
//        }
//        return new int[]{0};
//    }

    /*
    * 排序
    * 固定一个数 a
    * 在该数后面的区域，利用“双指针”快速找到两个的和等于 -a
    * 去重：找到一种结果之后，left、right 指针要跳过重复元素
    * 当使用完一次双指针算法之后，i 也需要跳过元素
    * 不漏：找到一种结果之后，不要停，缩小区间，继续寻找
    * */

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        //排序
        Arrays.sort(nums);
        //利用双指针解决问题
        int n = nums.length;
        for (int i = 0; i < n; ) {//固定数a
            if(nums[i] > 0){
                break;//小优化
            }
            int left = i + 1;
            int right = n - 1;
            int target = -nums[i];
            while(left < right){
                int sum = nums[left] + nums[right];
                if(sum > target){
                    right--;
                }else if(sum < target){
                    left++;
                }else{
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    //缩小区间继续寻找
                    left++;
                    right--;
                    //去重：left、right
                    while(nums[left] == nums[left - 1] && left < right){
                        left++;
                    }
                    while(nums[right] == nums[right + 1] && left < right){
                        right--;
                    }
                }
            }
            //去重：i
            i++;
            while(i < n && nums[i] == nums[i - 1]){
                i++;
            }
        }
        return ret;
    }


}
